package com.venusj.springbootredis;

import java.util.HashMap;
import java.util.Map;

/**
 * Lru实现就是一个map加上双向链表结构可以实现，AQS底层也是类似的
 *
 * @author venusj
 * @date 2021/3/26
 */
public class LRUCacheDemo {
    private int cacheSize;

    Map<Integer, Node<Integer, Integer>> map;
    DoubleLinkedList<Integer, Integer> doubleLinkedList;
    //map 负责查找，构建一个虚拟的双向链表，里面安装的就是一个Node节点，作为数据载体


    public LRUCacheDemo(int cacheSize, Map<Integer, Node<Integer, Integer>> map, DoubleLinkedList<Integer, Integer> doubleLinkedList) {
        this.cacheSize = cacheSize;  // 大小
        this.map = new HashMap<>(); // 查找
        this.doubleLinkedList = new DoubleLinkedList<>(); // 存放Node
    }

    public int get(int key)
    {
        if(!map.containsKey(key))
        {
            return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        // 重新在双向链表中排序
        doubleLinkedList.removeNode(node);
        doubleLinkedList.addHead(node);

        return node.value;
    }

    public void put(int key, int value)
    {
        // 存在key,则更新
        if(map.containsKey(key))
        {
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            map.put(key, node);

            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
        }
        else
        {
            // 不存在时
            if(map.size() == cacheSize)
            {
                Node lastNode = doubleLinkedList.getLast();
                map.remove(lastNode.key);
                doubleLinkedList.removeNode(lastNode);
            }
            // 开始新增
            Node<Integer, Integer> newNode = new Node<>(key, value);
            map.put(newNode.key, newNode);
            doubleLinkedList.addHead(newNode);
        }
    }

    // 1 构造一个Node节点，作为数据载体
    class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        public Node() {
            this.prev = this.next = null;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }

    // 2 构造一个DoubleLinkedList,里面放的是Node节点
    class DoubleLinkedList<K, V> {
        Node<K, V> tail;
        Node<K, V> head;

        public DoubleLinkedList() {
            tail = new Node<>();
            head = new Node<>();
        }

        // 添加到头结点
        public void addHead(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        // 删除节点
        public void removeNode(Node node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
            node.next = null;
            node.prev = null;
        }

        // 获得最后一个结点
        public Node getLast() {
            return tail.prev;
        }

    }

    public static void main(String[] args) {

    }
}
